Link
首先我们要能有一个算法进行预处理使我们能够快速的确定一个数在任意区间$[L, R]$内是否只出现了一次。
难么我们考虑预处理出这个数的前一个出现的位置和后一个出现的位置P和S，于是在判断的时候我们只需要判断(P < L && S > R)就可以了。
那么如何处理出两个数组？
我们用另一个数组$Last[A[i]]$表示$A[i]$最后一次出现的位置，于是就有
1 | R[Last[A[i]]] = i, |
于是我们就可以在$O(1)$的时间复杂度内完成上面说的那项事情了。
接下来我们进行分治，每次寻找出该区间内的某一个之出现过一次的值，找到即往左右分治即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std ;
typedef long long LL ;
const int MAXN = 2000010 ;
const int MAXM = 2000010 ;
const int INF = 0x7fffffff ;
int T, N, A[MAXN], L[MAXN], R[MAXN] ;
unordered_map <int, int> Last ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0')
F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9')
X = (X << 1) + (X << 3) + (ch ^ 48), ch = getchar() ;
return X * F ;
}
bool Judge(int X, int Y) {
int LL = X, RR = Y ;
if (X >= Y) return 1 ;
for (int i = X ; i <= Y ; i ++) {
if (i & 1) {
if (L[LL] < X && R[LL] > Y)
return Judge(X, LL - 1) && Judge(LL + 1, Y) ;
LL ++ ;
} else {
if (L[RR] < X && R[RR] > Y)
return Judge(X, RR - 1) && Judge(RR + 1, Y) ;
RR -- ;
}
}
return 0 ;
}
signed main() {
T = Read() ; while (T --) {
N = Read() ;
Last.clear() ;
for (int i = 1 ; i <= N ; i ++)
L[i] = - 1, R[i] = INF ;
for (int i = 1 ; i <= N ; i ++) A[i] = Read() ;
for (int i = 1 ; i <= N ; i ++) {
R[Last[A[i]]] = i,
L[i] = Last[A[i]],
Last[A[i]] = i ;
}
for (int i = 1 ; i <= N ; i ++)
R[Last[A[i]]] = N + 1 ;
if (Judge(1, N))
puts("non-boring") ;
else
puts("boring") ;
}
return 0 ;
}